COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.DEVICE XGP
C00012 ENDMK
C⊗;
.DEVICE XGP
.PAGE FRAME 54 HIGH 82 WIDE
.AREA TEXT LINE 1 TO 52
.FONT 1 "BDB30" 
.SELECT 1
.BEGIN CENTER

SYLLABUS FOR PH.D. QUALIFYING EXAMINATION
IN THE MATHEMATICAL ASPECTS OF COMPUTER SCIENCE

April 1974
.END
.INDENT 0,0
The examination will be held on May 25.  If there are few enough students
it wil be oral.  Otherwise it will be four hours, open book starting at 10 a.m.
.INDENT 0,0
.SKIP 1
1.  Mathematical Logic ([1] or [2], see the bibliography in [3.1]
.INDENT 7

1.1  The Propositional Calculus

1.2  The Predicate Calculus

1.3  Theorem Proving by Computers

.INDENT 0,0
2.  Theory of Computability ([4] or [5])
.INDENT 7,12

2.1  Church's Thesis and the equivalence of several definitions of
computability, such as Turing computable, Mrkov computable and
general recursive.

2.2  Primitive recursive and partial recursive functions.
Ackermann's function.  Recursive and recursively enumerable sets.

2.3  The Halting problem of Turing machines (and the equivalent
problem for recursive functions).

.INDENT 0,0
3.  Automata Theory and Computational Complexity (p[6]-[8])

.INDENT 7,12
3.1  Finite Automata (deteministic and non-deterministic), regular
expressions (Kleene Theorem), right-linear languages and finite
semi-groups.

3.2  Push-down automata (deterministic and non-deterministic) and
Context-free languages.  Linear bounded automata and context
sensitive languages.

3.3  Axiomatic computational complexity theory.

.INDENT 0,0
4.  Mathematical Theory of Computation
	
.INDENT 7,12
4.1  Methods for proving properties of:  Compilers, program schemas,
and programs.  ([9]-[16])

4.2  Semantics of Programming Languages. ([17]-[18])

4.3  Monotonic and Continuous Functions. ([21]-[22])

.NEXT PAGE
.INDENT 0,0
5.  Theory of Computation Complexity

.INDENT 7,12
5.1  Abstract comlexity theory

5.2  P=?NP

.INDENT 0,0
6. Mathematical Background

.INDENT 7,12
6.1  Algebra

6.2  Set Theory

.NEXT PAGE
.ONCE CENTER
REFERENCES
.SKIP 2

.INDENT 0,7
[1]  Mendelson, E., INTRODUCTION TO MATHEMATICAL LOGIC.  Van Nostrand (1964).

[2]  Robbin J. W., MATHEMATICAL LOGIC:  A FIRST COURSE. W. A. Benjamin (1969).

[3]  Robinson, J.A. "A Review of Automatic Theorem-Proving", in MATHEMATICAL
	ASPECTS OF COMPUTER SCIENCE.  American Mathematical Society (1967).

[4]  Davis, M., COMPUTABILITY AND UNSOLVABILITY.  McGraw-Hill (1958).

[5]  Hermes, H., ENUMERABILITY, DECIDABILITY AND COMPUTABILITY.  
Academic Press (1965).

[6]  Minsky, M., COMPUTATION:  FINITE AND INFINITE MACHINES.  Prentice-Hall (1967).

[7]  Rabin, M. O. and Scott, D., "Finite Automata and Their Decision Problems".
IBM JOURNAL 3, 114 (1959).  Also in SEQUENTIAL MACHINES (ed. E. F. Moore),
Addison-Wesley (1969).

[8]  Hopcroft, J. and Ullman J., FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA.
Addison-Wesley (1969).

[9]  McCarthy, J., and Painter, J., "Correctness of a Compiler for Arithmetic
Expressions". in PROCEEDINGS OF SYMPOSIA IN APPLIED MATHEMATICS, Vol. 19
(1967).

[10] Rutledge, J. D., "On Ianov Program Schemata." JOURNAL OF THE ACM, Vol. 11, 
No. 1 (1964), pp. 1-9.

[11] Luckham, D. C., Park, D. M. R. and Paterson, M. S., ON FORMALISED COMPUTER
PROGRAMS.  (Preliminary draft) Programming Research Group, Oxford University
(August 1967).

[12] Floyd, R. W., "Assigning Meaning to Programs". in MATHEMATICAL ASPECTS OF
COMPUTER SCIENCE.  American Mathematical Society (1967).

[13] McCarthy, J., "Towards a Mathematical Science of Computation." in PROCEEDINGS
IFIP CONGRESS 62, North-Holland, Amsterdam (1962), pp. 21-26.

[14] McCarthy, J., "Basis for a Mathematical Theory of Computation." in COMPUTER
PROGRAMMING AND FORMAL SYSTEMS (Braffort and Hirschberg, eds.), North-
Holland (1963), pp. 33-70

[15] Manna, Z., "Properties of Programs and the First-Order Predicate Calculus."
in JACM, Vol. 16, No.2 (April 1969).

[16] Manna, Z. and Pnueli, A., "Formalization of Properties of Functional Programs".
in ACM SYMPOSIUM ON THEORY OF COMPUTING (May 1969).

[17] McCarthy, J., "A Formal Description of a Subset of Algol". in FORMAL LANGUAGE
DESCRIPTION LANGUAGES FOR COMPUTER PROGRAMMING.  (Steele, ed.). North-
Holland (1966).

[18] Lucas, P., Lauer, P., Stigleitner, H., METHOD AND NOTATION FOR THE FORMAL
DEFINITION OF PROGRAMMING LANGUAGES.  IBM Lab, Vienna, TR 25.087 (June 1968).

[20] Hartmanis, Juris and Hopcroft, John E, "An Overview of Theory of Computational
Complexity", JACM, Vol. 18, 1971, p. 444-475.

[21] Scott, D., and Strachey, C., "Towards a Mathematical Semantics for Computer
Languages", in PROC. SYMP. ON COMPUTERS AND AUTOMATA, Polytechnic
Institute of Brooklyn, 1972.

[22] Weyhrauch, Richard and Milner, Robin, "Program Semantics and Correctness in a
Mechanized Logic", in FIRST USA-JAPAN COMPUTER CONFERENCE PROCEEDINGS, AFIPS
and IPSJ, l972.

[23] Blum, Manuel, "A Machine-Independent Theory of the Complexity of Recursive
Functions, JACM, Vol 14, 1967, pp. 322-336
.NEXT PAGE
.INDENT 7
.ONCE CENTER
RECOMMENDED COURSES:

Phil. 160 AB, 162

CS 156; CS 256, 257, 258, 259

Theory of Computation Seminar

.ONCE CENTER

RELATED COURSES:

EE 484

Math 292 ABC, 293 ABC